package com.wzw.basics.sort;

import java.util.Arrays;

/**
 * 选择排序: 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
 *
 * @author Wangzhiwen
 */
public class SelectionSort {

    /**
     *
     * 10,3,123,43,56,12,9 length=7 [0,6]
     *
     * i=0 0<j=i<7
     * j=0 minIndex=0 10 3 123 43 56 12 9 -> minIndex=0
     * j=1 minIndex=0 10 3 123 43 56 12 9 -> minIndex=1
     * j=2 minIndex=1
     * j=3 minIndex=1
     * j=4 minIndex=1
     * j=5 minIndex=1
     * j=6 minIndex=1
     * swap arrays[0] arrays[1] -> 3 10 123 43 56 12 9
     *
     * i=1 0<j=i=1<7
     * 3 10 123 43 56 12 9
     * j=1 minIndex=1 3 10 123 43 56 12 9 -> minIndex=1
     * j=2 minIndex=1 -> minIndex=1
     * j=3 minIndex=1 -> minIndex=1
     * j=4 minIndex=1 -> minIndex=1
     * j=5 minIndex=1 -> minIndex=1
     * j=6 minIndex=1 -> midIndex=6
     * swap arrays[1] arrays[6] -> 3 9 123 43 56 12 10
     *
     * i=2 0<j=i=2<7 minIndex=2
     * 3 9 123 43 56 12 10
     * j=2 minIndex=2 -> minIndex=2
     * j=3 minIndex=2 -> minIndex=3
     * j=4 minIndex=3 -> minIndex=3
     * j=5 minIndex=3 -> minIndex=5
     * j=6 minIndex=5 -> minIndex=6
     * swap arrays[2] arrays[6] -> 3 9 10 43 56 12 123
     */
    public static void execute(int[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }
        // 1.每一次循环后都会把最小（大）的元素放在最前面
        for (int i = 0; i < arrays.length; i++) {
            /*
             * minIndex: 记录当次循环比较元素值是最小的下标，初始化为第一次循环 i 的值
             * int j=i : 外层循环过一次后，最小的元素已经放在了最前面，所以这里无需在和已排好序的元素比较（后面的元素一定比前面的大）
             * int j=i+1 : 最开始j=i，第一次进入循环时取到的arrays[j] arrays[minIndex]是同一个元素，也就是可以不用比较了
             * minIndex : 当次最小元素的下标值
             */
            int minIndex = i;
            for (int j = i+1; j < arrays.length; j++) {
                if (arrays[j] < arrays[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换当前值与最小元素值的位置，已达到排序的目的
            int temp = arrays[minIndex];
            arrays[minIndex] = arrays[i];
            arrays[i] = temp;
        }
        System.out.println("selection sort " + Arrays.toString(arrays));
    }

}
